﻿#region Imported Libraries

#endregion
namespace org.webguvenligi.NSecureImageLib.GraphicFileFormats.PNG.Compression
{
    /// <summary>
    /// This Parts Are Taken From IBM's SWT Implementation Engine
    /// </summary>
    public class PngHuffmanTable
    {
        CodeLengthInfo[] codeLengthInfo;
        int[] codeValues;
        const int MAX_CODE_LENGTH = 15;
        const int BAD_CODE = 0xFFFFFFF;
        public PngHuffmanTable(int[] lengths)
        {
            initialize(lengths);
            GenerateTable(lengths);
        }
        private void initialize(int[] lengths)
        {
            codeValues = new int[lengths.Length];
            for (int i = 0; i < codeValues.Length; i++)
            {
                codeValues[i] = i;
            }
            // minCodesByLength[n] : The smallest Huffman code of length n + 1.
            // maxCodesByLength[n] : The largest Huffman code of length n + 1.
            // indexesByLength[n] : Index into the values array. First value with a code of length n + 1.
            codeLengthInfo = new CodeLengthInfo[MAX_CODE_LENGTH];
            for (int i = 0; i < MAX_CODE_LENGTH; i++)
            {
                codeLengthInfo[i] = new CodeLengthInfo();
                codeLengthInfo[i].length = i;
                codeLengthInfo[i].baseIndex = 0;
                codeLengthInfo[i].min = BAD_CODE;
                codeLengthInfo[i].max = -1;
            }
        }

        private void GenerateTable(int[] lengths)
        {
            // Sort the values. Primary key is code size. Secondary key is value.
            for (int i = 0; i < lengths.Length - 1; i++)
            {
                for (int j = i + 1; j < lengths.Length; j++)
                {
                    if (lengths[j] < lengths[i]
                        || (lengths[j] == lengths[i]
                        && codeValues[j] < codeValues[i]))
                    {
                        int tmp;
                        tmp = lengths[j];
                        lengths[j] = lengths[i];
                        lengths[i] = tmp;
                        tmp = codeValues[j];
                        codeValues[j] = codeValues[i];
                        codeValues[i] = tmp;
                    }
                }
            }

            // These values in these arrays correspond to the elements of the
            // "values" array. The Huffman code for codeValues[N] is codes[N]
            // and the length of the code is lengths[N].
            int[] codes = new int[lengths.Length];
            int lastLength = 0;
            int code = 0;
            for (int i = 0; i < lengths.Length; i++)
            {
                while (lastLength != lengths[i])
                {
                    lastLength++;
                    code <<= 1;
                }
                if (lastLength != 0)
                {
                    codes[i] = code;
                    code++;
                }
            }

            int last = 0;
            for (int i = 0; i < lengths.Length; i++)
            {
                if (last != lengths[i])
                {
                    last = lengths[i];
                    codeLengthInfo[last - 1].baseIndex = i;
                    codeLengthInfo[last - 1].min = codes[i];
                }
                if (last != 0) codeLengthInfo[last - 1].max = codes[i];
            }
        }

        //TODO Open Here Later
        public int getNextValue(PngDecodingDataStream stream)
        {
            int code = stream.getNextIdatBit();
            int codelength = 0;

            // Here we are taking advantage of the fact that 1 bits are used as
            // a prefix to the longer codeValues.
            while (codelength < MAX_CODE_LENGTH && code > codeLengthInfo[codelength].max)
            {
                code = ((code << 1) | stream.getNextIdatBit());
                codelength++;
            }
            if (codelength >= MAX_CODE_LENGTH) stream.error();

            // Now we have a Huffman code of length (codelength + 1) that
            // is somewhere in the range
            // minCodesByLength[codelength]..maxCodesByLength[codelength].
            // This code is the (offset + 1)'th code of (codelength + 1);
            int offset = code - codeLengthInfo[codelength].min;

            // indexesByLength[codelength] is the first code of length (codelength + 1)
            // so now we can look up the value for the Huffman code in the table.
            int index = codeLengthInfo[codelength].baseIndex + offset;
            return codeValues[index];
        }

        class CodeLengthInfo
        {
            public int length
            {
                get;
                set;
            }
            public int max
            {
                get;
                set;
            }
            public int min
            {
                get;
                set;
            }
            public int baseIndex
            {
                get;
                set;
            }
        }
    }
}
